<!DOCTYPE html>
<html lang="en">
<head>
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
    <meta charset="UTF-8">
    <title>A*寻路算法</title>
    <style>
        #stage {
            border: 1px solid lightgray;
        }
    </style>
</head>
<body>
<canvas id="stage"></canvas>
</body>
<script>
    window.onload = function () {
        var stage = document.querySelector('#stage'),
            ctx = stage.getContext('2d');
        stage.width = 600;
        stage.height = 600;
        var row = 7, column = 7, r = 40;

        //取区域随机数x>=min && x<max
        function randInt(min, max) {
            max = max || 0;
            min = min || 0;
            var step = Math.abs(max - min);
            var st = (arguments.length < 2) ? 0 : min;//参数只有一个的时候，st = 0;
            var result;
            result = st + (Math.ceil(Math.random() * step)) - 1;
            return result;
        }

        //普里姆算法生成连通图的二维数组 row 行 column 列
        function primMaze(r, c) {
            //初始化数组
            function init(r, c) {
                var a = new Array(2 * r + 1);
                //全部置1
                for (let i = 0, len = a.length; i < len; i++) {
                    var cols = 2 * c + 1;
                    a[i] = new Array(cols);
                    for (let j = 0, len1 = a[i].length; j < len1; j++) {
                        a[i][j] = 1;
                    }
                }
                //中间格子为0
                for (let i = 0; i < r; i++)
                    for (let j = 0; j < c; j++) {
                        a[2 * i + 1][2 * j + 1] = 0;
                    }
                return a;
            }

            //处理数组，产生最终的数组
            function process(arr) {
                //acc存放已访问队列，noacc存放没有访问队列
                var acc = [], noacc = [];
                var r = arr.length >> 1, c = arr[0].length >> 1;
                var count = r * c;
                for (var i = 0; i < count; i++) {
                    noacc[i] = 0;
                }
                //定义空单元上下左右偏移
                var offs = [-c, c, -1, 1], offR = [-1, 1, 0, 0], offC = [0, 0, -1, 1];
                //随机从noacc取出一个位置
                var pos = randInt(count);
                noacc[pos] = 1;
                acc.push(pos);
                while (acc.length < count) {
                    var ls = -1, offPos = -1;
                    offPos = -1;
                    //找出pos位置在二维数组中的坐标
                    var pr = pos / c | 0, pc = pos % c, co = 0, o = 0;
                    //随机取上下左右四个单元
                    while (++co < 5) {
                        o = randInt(0, 5);
                        ls = offs[o] + pos;
                        var tpr = pr + offR[o];
                        var tpc = pc + offC[o];
                        if (tpr >= 0 && tpc >= 0 && tpr <= r - 1 && tpc <= c - 1 && noacc[ls] == 0) {
                            offPos = o;
                            break;
                        }
                    }
                    if (offPos < 0) {
                        pos = acc[randInt(acc.length)];
                    } else {
                        pr = 2 * pr + 1;
                        pc = 2 * pc + 1;
                        //相邻空单元中间的位置置0
                        arr[pr + offR[offPos]][pc + offC[offPos]] = 0;
                        pos = ls;
                        noacc[pos] = 1;
                        acc.push(pos);
                    }
                }
            }

            var a = init(r, c);
            process(a);
            return a;
            //返回一个二维数组，行的数据为2r+1个,列的数据为2c+1个
        }

        //栅格线条
        function drawGrid(context, color, stepx, stepy) {
            context.strokeStyle = color;
            context.lineWidth = 0.5;
            for (var i = stepx + 0.5; i < context.canvas.width; i += stepx) {
                context.beginPath();
                context.moveTo(i, 0);
                context.lineTo(i, context.canvas.height);
                context.stroke();
            }
            for (var i = stepy + 0.5; i < context.canvas.height; i += stepy) {
                context.beginPath();
                context.moveTo(0, i);
                context.lineTo(context.canvas.width, i);
                context.stroke();
            }
        }

        //方块创造方法
        function createRect(x, y, r, c) {
            ctx.beginPath();
            ctx.fillStyle = c;
            ctx.rect(x, y, r, r);
            ctx.fill();
        }

        //定义点对象【a*点对象】
        function Point(x, y) {
            this.x = x;
            this.y = y;
            this.parent = null;
            this.f = 0;
            this.g = 0;
            this.h = 0;
            //当前点状态，0：表示在openlist 1:表示closelist,-1表示还没处理
            this.state = -1;
            //flag表明该点是否可通过
            this.flag = 0;
        }

        //把普通二维数组(全部由1，0表示)的转换成a*所需要的点数组
        function convertArrToAS(arr) {
            var r = arr.length, c = arr[0].length;
            var a = new Array(r);
            for (var i = 0; i < r; i++) {
                a[i] = new Array(c);
                for (var j = 0; j < c; j++) {
                    var pos = new Point(i, j);
                    pos.flag = arr[i][j];
                    a[i][j] = pos;
                }
            }
            return a;
        }

        //A*算法,pathArr表示最后返回的路径
        function findPathA(pathArr, start, end, row, col) {
            console.log('findPathA')
            // console.log('pathArr',pathArr,'start',start,'end',end,'row',row,'col',col)
            //添加数据到排序数组中
            function addArrSort(descSortedArr, element, compare) {
                var left = 0;
                var right = descSortedArr.length - 1;
                while (left <= right) {
                    var mid = (left + right) >> 1;
                    console.log('left', left, 'right', right, 'mid', mid)
                    if (compare(descSortedArr[mid], element) == 1) {
                        left = mid + 1;
                    } else if (compare(descSortedArr[mid], element) == -1) {
                        right = mid - 1;
                    } else {
                        break;
                    }
                }
                for (var i = descSortedArr.length - 1; i >= left; i--) {
                    descSortedArr[i + 1] = descSortedArr[i];
                }
                descSortedArr[left] = element;
            }

            //判断两个点是否相同
            function pEqual(p1, p2) {
                return p1.x == p2.x && p1.y == p2.y;
            }

            //获取两个点距离，采用曼哈顿方法
            function posDist(pos, pos1) {
                return (Math.abs(pos1.x - pos.x) + Math.abs(pos1.y - pos.y));
            }

            function between(val, min, max) {
                return (val >= min && val <= max)
            }

            //比较两个点f值大小
            function compPointF(pt1, pt2) {
                return pt1.f - pt2.f;
            }

            //处理当前节点
            function processCurrpoint(arr, openList, row, col, currPoint, destPoint) {
                console.log('processCurrpoint')
                //get up,down,left,right direct
                var ltx = currPoint.x - 1;
                var lty = currPoint.y - 1;
                for (var i = 0; i < 3; i++) {
                    for (var j = 0; j < 3; j++) {
                        var cx = ltx + i;
                        var cy = lty + j;
                        if ((cx === currPoint.x || cy === currPoint.y) &&
                            between(ltx, 0, row - 1) &&
                            between(lty, 0, col - 1)) {
                            var tp = arr[cx][cy];
                            if (tp.flag === 0 && tp.state !== 1) {
                                if (pEqual(tp, destPoint)) {
                                    tp.parent = currPoint;
                                    return true;
                                }
                                if (tp.state === -1) {
                                    tp.parent = currPoint;
                                    tp.g = 1 + currPoint.g;
                                    tp.h = posDist(tp, destPoint);
                                    tp.f = tp.h + tp.f;
                                    tp.state = 0;
                                    addArrSort(openList, tp, compPointF);
                                } else {
                                    var g = 1 + currPoint.g;
                                    if (g < tp.g) {
                                        tp.parent = currPoint;
                                        tp.g = g;
                                        tp.f = tp.g + tp.h;
                                        openList.quickSort(compPointF);
                                    }
                                }
                            }
                        }
                    }
                }
                return false;
            }

            //定义openList
            var openList = [];
            //定义closeList
            var closeList = [];
            start = pathArr[start[0]][start[1]];
            end = pathArr[end[0]][end[1]];
            //添加开始节点到openList;
            addArrSort(openList, start, compPointF);
            console.log('openList', openList)
            var finded = false;
            while ((openList.length > 0)) {
                var currPoint = openList.pop();
                currPoint.state = 1;
                closeList.push(currPoint);
                finded = processCurrpoint(pathArr, openList, row, col, currPoint, end);
                console.log('finded', finded)
                if (finded) {
                    break;
                }
            }
            if (finded) {
                var farr = [];
                var tp = end.parent;
                farr.push(end);
                while (tp != null) {
                    // console.log('tp',tp)
                    farr.push(tp);
                    tp = tp.parent;
                }
                // console.log('farr',farr)
                return farr;
            }
            else {
                return null;
            }
        }

        //定位屏幕坐标到数组位置
        function mapSCPos(i, j) {
            // console.log('i',i,'j',j,'r',r)
            return [i / r | 0, j / r | 0];
        }

        //检测数组中的位置是否存在方块
        function mapHasRect(map, i, j) {
            return (map[i][j]);
        }

        var mapArr = primMaze(row, column);
        var startRect = {
                x: function () {
                    for (var i = 0, len = mapArr.length; i < len; i++) {
                        for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
                            if (!mapArr[i][j]) {
                                return j * r;
                                break;
                            }
                        }
                    }
                }(),
                y: function () {
                    for (var i = 0, len = mapArr.length; i < len; i++) {
                        for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
                            if (!mapArr[i][j]) {
                                return i * r;
                                break;
                            }
                        }
                    }
                }(),
                pos: function () {
                    return [this.x, this.y];
                }
            },
            endRect = {
                hasCreate: false,
                x: null,
                y: null,
                pos: function () {
                    return [this.x, this.y];
                }
            },
            startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]),
            endPoint,
            path = null,
            next = null;

        //计算路经
        function update() {
            ctx.clearRect(0, 0, 600, 600);
            drawGrid(ctx, 'lightgray', r, r);
            // console.log('mapArr',mapArr)
            //根据地图二维数组创建色块
            for (var i = 0, len = mapArr.length; i < len; i++) {
                for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
                    if (mapArr[i][j]) {
                        createRect(j * r, i * r, r, "black");
                    }
                }
            }
            //绘制开始方块
            createRect(startRect.x, startRect.y, r, "red");
            if (endRect.hasCreate) {
                //绘制跟随方块
                createRect(endRect.pos()[0], endRect.pos()[1], r, "blue");
                endPoint = mapSCPos(endRect.pos()[1], endRect.pos()[0]);

                if (path === null) {
                    var ASmap = convertArrToAS(mapArr);
                    path = findPathA(ASmap, startPoint, endPoint, ASmap.length, ASmap.length);
                    // console.log('path',path)
                } else {
                    next = path.pop();
                    startRect.y = next.x * r;
                    startRect.x = next.y * r;
                    if (path.length === 0) {
                        startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]);
                        path = null;
                        endRect.hasCreate = false;
                    }
                }
            }
            requestAnimationFrame(update);
        }

        update();
        stage.addEventListener('click', function () {
            //标准的获取鼠标点击相对于canvas画布的坐标公式
            var x = event.clientX - stage.getBoundingClientRect().left,
                y = event.clientY - stage.getBoundingClientRect().top;
            var endRectPos = mapSCPos(y, x);//[i,j]
            // console.log('endRectPos',endRectPos)
            endRect.x = endRectPos[1] * r;
            endRect.y = endRectPos[0] * r;
            if (mapHasRect(mapArr, endRectPos[0], endRectPos[1])) {
                console.log('这个位置已经有方块啦！');
            } else {
                endRect.pos();
                endRect.hasCreate = true;
            }
        })
    };
</script>
</html>
